//1087
#include <string>
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;
const int maxn=210;
const int INF=100000000;

int N,K,cnt=0,value=-1;
double avgvalue;
map<string,int> cities;
map<int,string> mmap;
vector<int> num, values, dis, temppath, path;// i starts from 1
vector<vector<int> > pre;// i starts from 1
int g[maxn][maxn]; // i,j starts from 1
vector<bool> visit;// i starts from 1

void dfs(int v)
{
	temppath.push_back(v); // 入栈 
	if(v==1) // 从终点逆序递归到起点 
	{
		int totalvalue=0;
		for(int i=0;i<temppath.size();i++)
		{
			totalvalue += values[temppath[i]];
		}
		double tempavgval = 1.0*totalvalue/(temppath.size()-1);
		if(totalvalue > value)
		{
			value = totalvalue;
			path = temppath;
			avgvalue = tempavgval;
		}
		
		temppath.pop_back(); // 到底起点，return 函数出口前都要记得出栈 
		return; 
	}
	for(int i=0;i<pre[v].size();i++)
	{
		dfs(pre[v][i]);
	}
	temppath.pop_back(); // 出栈 上层回溯 
}

int main(void)
{
//	freopen("f:/tmp/PAT/1.txt","r",stdin);
	scanf("%d%d",&N,&K);
	int val, cost;
	char city[4], city1[4], city2[4];
	values.resize(N+1);
	pre.resize(N+1);
	num.resize(N+1, 0);
	visit.resize(N+1, false);
	dis.resize(N+1, INF); // INF
	fill(g[0], g[0]+maxn*maxn, INF);//INF
	scanf("%s",city);
	cities.insert(make_pair(city, 1));
	mmap.insert(make_pair(1, city));
	values[1]=0;
	for(int i=1;i<N;i++)
	{
		scanf("%s%d",city,&val);
		cities.insert(make_pair(city, i+1));
		mmap.insert(make_pair(i+1, city));
		values[i+1] = val;
	}
	for(int i=0;i<K;i++)
	{
		scanf("%s%s%d",city1,city2,&cost);
		g[cities[city1]][cities[city2]] = cost;
		g[cities[city2]][cities[city1]] = cost;
	}

	dis[1]=0; num[1]=1;// start
	for(int i=1;i<=N;i++)
	{
		int u=-1,minn=INF;
		for(int j=1;j<=N;j++)
		{
			if(!visit[j] && dis[j] < minn)
			{
				u = j;
				minn = dis[j];
			}
		}
		if(u==-1) break;
		visit[u]=true;
		for(int v=1;v<=N;v++)
		{
			if(!visit[v] && g[u][v]!=INF) // 未访问并且可达，可达不能忘记 
			{
				if(dis[u] + g[u][v] < dis[v])
				{
					dis[v] = dis[u] + g[u][v];
					pre[v].clear();
					pre[v].push_back(u);
					num[v] = num[u];
				}else if(dis[u] + g[u][v] == dis[v])
				{
					pre[v].push_back(u);
					num[v] += num[u];
				}
			}
		}
	}

	int rom = cities["ROM"];
	dfs(rom);
	printf("%d %d %d %d\n",num[rom],dis[rom],value,(int)avgvalue);
	for(int i = path.size() - 1; i >= 1; i--) {
        printf("%s->",mmap[path[i]].c_str());
    }
    printf("ROM");
	return 0;
}